//给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。 
//
// 两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串： 
//
// 
// s = s1 + s2 + ... + sn 
// t = t1 + t2 + ... + tm 
// |n - m| <= 1 
// 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ... 
// 
//
// 提示：a + b 意味着字符串 a 和 b 连接。 
//
// 
//
// 示例 1： 
//
// 
//输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
//输出：false
// 
//
// 示例 3： 
//
// 
//输入：s1 = "", s2 = "", s3 = ""
//输出：true
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s1.length, s2.length <= 100 
// 0 <= s3.length <= 200 
// s1、s2、和 s3 都由小写英文字母组成 
// 
// Related Topics 字符串 动态规划 
// 👍 506 👎 0

package leetcode.editor.cn;

/**
 * Java：交错字符串
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P97_InterleavingString {
    public static void main(String[] args) {
        Solution solution = new P97_InterleavingString().new Solution();
        // TODO 此处开始你的表演

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isInterleave(String s1, String s2, String s3) {
            if (s1 == null || s2 == null || s3 == null) {
                return false;
            }
            int N1 = s1.length();
            int N2 = s2.length();
            int N3 = s3.length();

            if (N1 + N2 != N3) {
                return false;
            }
            char[] c1 = s1.toCharArray();
            char[] c2 = s2.toCharArray();
            char[] c3 = s3.toCharArray();
            boolean[][] dp = new boolean[N1 + 1][N2 + 1];
            dp[0][0] = true;
            for (int i = 1; i <= N1; i++) {
                dp[i][0] = dp[i - 1][0] ? c1[i - 1] == c3[i - 1] : false;
            }
            for (int j = 1; j <= N2; j++) {
                dp[0][j] = dp[0][j - 1] ? c2[j - 1] == c3[j - 1] : false;
            }
            for (int i = 1; i <= N1; i++) {
                for (int j = 1; j <= N2; j++) {
                    // i的最后一个和c3的相等
                    boolean p1 = (c1[i - 1] == c3[i + j - 1]) && (dp[i][j] = dp[i - 1][j]);
                    // j的最后一个和c3相等
                    boolean p2 = (c2[j - 1] == c3[i + j - 1]) && (dp[i][j] = dp[i][j - 1]);
                    // 两者求或
                    dp[i][j] = p1 || p2;
                }
            }
            return dp[N1][N2];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}